/**
 * 二叉树的双旋操作
 *
 * 左右双旋：
 * - 当要对某个节点进行左单旋时，如果变化分支是唯一的最深分支，
 *   那么我们要对新跟进行右单旋，然后再进行左单旋，这样的旋转叫做右左双旋
 *
 * 右左双旋：
 * - 当要对某个节点进行右单旋时，如果变化分支是唯一的最深分支，
 *   那么我们要对新跟进行左单旋，然后再进行右单旋，这样的旋转叫做左右双旋
 *
 */


class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const a = new TreeNode("a");
const b = new TreeNode("b");
const c = new TreeNode("c");
const d = new TreeNode("d");
const e = new TreeNode("e");
a.left = b;
b.left = c;
c.left = d;
d.left = e;


/**
 * 计算二叉树的最大深度
 * @param {TreeNode} root - 二叉树的根节点
 * @returns {number} 返回二叉树的最大深度
 */
function getDeep(root) {
  // 如果节点为空，则深度为0
  if (root == null) return 0;
  // 递归计算左右子树的最大深度，并取较大值加1
  return Math.max(getDeep(root.left), getDeep(root.right)) + 1;
}

/**
 * 判断二叉树是否平衡
 * @param {TreeNode} root - 二叉树的根节点
 * @returns {boolean} 如果二叉树是平衡的返回true，否则返回false
 */
function isBalance(root) {
  // 如果节点为空，则认为是平衡的
  if (root == null) return true;
  // 计算左子树的深度
  let leftDeep = getDeep(root.left);
  // 计算右子树的深度
  let rightDeep = getDeep(root.right);
  // 如果左右子树深度差超过1，则不平衡
  if (Math.abs(leftDeep - rightDeep) > 1) return false;
  // 递归判断左右子树是否平衡
  return isBalance(root.left) && isBalance(root.right);
}


/**
 * 执行一次左旋转操作
 * 左旋转常用于平衡二叉树，如AVL树，在插入或删除节点后以恢复树的平衡
 * 左旋转操作针对的是一个右重（右子树较左子树深）的节点，通过旋转使其左子树更深
 *
 * @param {TreeNode} root - 需要进行左旋转的根节点
 * @returns {TreeNode} - 旋转后的根节点
 */
function leftRotate(root) {
  // 新的根节点将是当前节点的右子节点
  let newRoot = root.right;
  // 原根节点的右子节点变为新根节点的左子节点
  root.right = root.right.left;
  // 新根节点的左子节点变为原根节点
  newRoot.left = root;
  // 返回新的根节点
  return newRoot;
}


/**
 * 执行一次右旋转操作，用于平衡二叉树
 * 右旋转操作通常用于处理树的左子树比右子树高的情况，以平衡树的高度
 * @param {TreeNode} root - 需要进行右旋转的节点，假设该节点及其左子树已经存在
 * @returns {TreeNode} - 旋转后的根节点，即原来的左子节点
 */
function rightRotate(root) {
  // 将左子节点设为新的根节点
  let newRoot = root.left;
  // 原根节点的左子节点变为原左子节点的右子节点
  root.left = root.left.right;
  // 新根节点的右子节点设为原根节点
  newRoot.right = root;
  // 返回新的根节点
  return newRoot;
}


/**
 * 将给定的二叉树转换为平衡二叉树
 * 如果给定的根节点已经是平衡的，则直接返回该根节点
 * 否则，递归地对左右子树进行转换，直到整棵树变为平衡二叉树
 * @param {TreeNode} root - 二叉树的根节点
 * @returns {TreeNode} - 平衡化之后的二叉树的根节点
 */
function change(root) {
  console.log("▶『root』", root);
  // 检查当前根节点是否已经是平衡的
  if (isBalance(root)) return root;
  // 对左子树进行递归调用，以确保左子树也是平衡的
  if (root.left != null) root.left = change(root.left);
  // 对右子树进行递归调用，以确保右子树也是平衡的
  if (root.right != null) root.right = change(root.right);
  // 计算左子树的深度
  let leftDeep = getDeep(root.left);
  // 计算右子树的深度
  let rightDeep = getDeep(root.right);
  // 如果左右子树的深度差小于2，则当前根节点已经是平衡的
  if (Math.abs(leftDeep - rightDeep) < 2) {
    return root;
  } else if (leftDeep > rightDeep) {
    let changeTreeDeep = getDeep(root.left.right);
    let noChangeTreeDeep = getDeep(root.left.left);
    if (changeTreeDeep > noChangeTreeDeep) {
      root.left = leftRotate(root.left);
    }
    return rightRotate(root);
  } else {
    let changeTreeDeep = getDeep(root.right.left);
    let noChangeTreeDeep = getDeep(root.right.right);
    if (changeTreeDeep > noChangeTreeDeep) {
      root.right = rightRotate(root.right);
    }
    return leftRotate(root);
  }
}

console.log("▶『isBalance 前』", isBalance(a));
const newRoot = change(a);
console.log("▶『isBalance 后』", isBalance(a));
console.log("▶『newRoot』", newRoot);
